package com.leetcode.algorithm.y19.m02;

import java.util.Arrays;
import java.util.Stack;

/**
 * leetcode-cn.com
 * (done)739. 每日温度
 * (done)503. 下一个更大元素 II
 * @author: jie.deng
 * @time: 2019年2月20日 上午11:00:45
 */
public class MySolution0219 {

	/**
	 * 739. 每日温度
	 * 
	 * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。
	 * 
	 * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
	 * 
	 * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。
	 * @param T
	 * @return
	 */
	public int[] dailyTemperatures(int[] T) {
		int len = T.length;
		int[] ret = new int[len];
		Stack<NumAndIdx> stack = new Stack<NumAndIdx>();
		for (int i = 0; i < len; i++) {
			while (!stack.isEmpty()) {
				NumAndIdx cur = stack.peek();
				if (T[i] > cur.getNum()) {
					ret[cur.getIdx()] = i - cur.getIdx();
					stack.pop();
				} else {
					break;
				}
			}
			stack.push(new NumAndIdx(i, T[i]));
		}
		return ret;
	}
	
	class NumAndIdx{
		
		private int idx;
		private int num;
		
		public NumAndIdx(int idx, int num) {
			super();
			this.idx = idx;
			this.num = num;
		}

		public int getIdx() {
			return idx;
		}

		public void setIdx(int idx) {
			this.idx = idx;
		}

		public int getNum() {
			return num;
		}

		public void setNum(int num) {
			this.num = num;
		}

	}

	/**
	 * 503. 下一个更大元素 II
	 * 
	 * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
	 * 
	 * 示例 1:
	 * 
	 * 输入: [1,2,1]
	 * 输出: [2,-1,2]
	 * 解释: 第一个 1 的下一个更大的数是 2；
	 * 数字 2 找不到下一个更大的数； 
	 * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
	 * @param nums
	 * @return
	 */
	public int[] nextGreaterElements(int[] nums) {
		int len = nums.length;
		int[] ngArr = new int[len];
		Arrays.fill(ngArr, -1);

		Stack<NumAndIdx> stack = new Stack<NumAndIdx>();
		for (int i = 0; i < len; i++) {
			while (!stack.isEmpty()) {
				NumAndIdx cur = stack.peek();
				if (nums[i] > cur.getNum()) {
					ngArr[cur.getIdx()] = nums[i];
					stack.pop();
				} else {
					break;
				}
			}
			stack.push(new NumAndIdx(i, nums[i]));
		}

		if (!stack.isEmpty()) {
			for (int i = 0; i < len; i++) {
				while (!stack.isEmpty()) {
					NumAndIdx cur = stack.peek();
					if (nums[i] > cur.getNum()) {
						ngArr[cur.getIdx()] = nums[i];
						stack.pop();
					} else {
						break;
					}
				}
			}
		}

		return ngArr;
	}
    
}
